package com.zzw.algorithm.tree;

import org.junit.Test;
import java.util.*;

/**
 * created by zzw
 */
public class PreTree <K,V> {

    private TreeNode<K, V> root;

    public void createTree(List<K> keys, List<V> values) throws Exception {
        Queue<TreeNode<K,V>> queue = new LinkedList<TreeNode<K,V>>();
        // 如果两个列表大小不一样或者为空，抛出异常
        if (keys.size() != values.size() && keys.isEmpty() && values.isEmpty())
            throw new Exception("Inputs' scale are not equal.");
        // 如果root为空，创建root
        if (root == null)
            root = new TreeNode<K,V>(keys.get(0), values.get(0));
        TreeNode<K,V> p = root;
        // 创建树结构
        for (int i = 1; i < keys.size(); i ++) {
            // 如果节点为空，寻找下一个不为空的节点，回滚i的值
            if (p == null && !queue.isEmpty()) {
                p = queue.poll();
                i --;
                continue;
            }
            if (p.left == null) {
                p.left = new TreeNode<K,V>(keys.get(i), values.get(i));
                queue.offer(p.left);
            } else if (p.right == null) {
                p.right = new TreeNode<K,V>(keys.get(i), values.get(i));
                queue.offer(p.right);
            } else {
                if (!queue.isEmpty()) {
                    // 如果节点有左右子树，寻找下一个节点，回滚i的值
                    p = queue.poll();
                    i --;
                }
            }
        }
    }

    public TreeNode<K,V> getRoot() {
        return root;
    }

    // 前序遍历 递归
    public void preorderRecursion(TreeNode<K,V> parent) {
        if (parent == null) return;
        System.out.println(parent.toString());
        preorderRecursion(parent.left);
        preorderRecursion(parent.right);
    }

    // 前序遍历 非递归
    public void preorder() {
        if (root == null) return;
        Stack<TreeNode<K,V>> stack = new Stack<TreeNode<K,V>>();
        TreeNode<K,V> p = root;
        while (p != null) {
            System.out.println(p.toString());
            if (p.right != null) stack.push(p.right);
            p = p.left;
            if (p == null && !stack.isEmpty()) {
                p = stack.pop();
            }
        }
    }

    @Test
    public void preorderTest() throws Exception {
        List<Integer> keys = new ArrayList<Integer>();
        List<String> values = new ArrayList<String>();
        for (int i = 0; i < 10; i ++) {
            keys.add(i);
            values.add(i + "");
        }
        PreTree<Integer, String> tree = new PreTree<Integer, String>();
        tree.createTree(keys, values);
        tree.preorderRecursion(tree.getRoot());
        tree.preorder();
    }
}
